package pack2;

import java.util.Arrays;

public class selectSort {
    public static void main(String[] args) {
        int[]heap={1,5,4,3,7,6};
        int[] array = {99, 4, 5, 6, 1, 3, 2, 8, 5, 4, 1, 3, 1, 8, 4, 7, 1, 9};
        int[] bad = {99, 88, 55, 22, 11, 8, 7, 4, 3, 2, 1};
        //int[] arr=insertSort(bad);

//        int[] arr = chooseSort(bad);
//        System.out.println(Arrays.toString(arr));
        int[]arr=heapSort(bad);
        //creatHeap(heap);
        System.out.println(Arrays.toString(arr));

    }

    /**排序大分类：《选择排序》
     * 插入排序
     * 时间复杂度：(n^2),不管什么情况下都是这个，因为都次都要要逐个遍历数组
     * 稳定性：不稳定的
     * 适用场合：
     * @param array 待排序数组
     * @return 返回排序好的数组
     */

    public static int[] chooseSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            if ( array[i]>array[minIndex]) {
                int temp = array[minIndex];
                array[minIndex]= array[i];
                array[i] = temp;
            }

        }
        return array;
    }


    /**排序大分类：《堆排序》
     * 插入排序
     * 时间复杂度：(n*log2N),不管什么情况下都是这个，因为都次都要要逐个遍历数组
     * 稳定性：不稳定的
     * 适用场合：
     * @param array 待排序数组
     * @return 返回排序好的数组
     */
    public static int[]heapSort(int[]array){
        //创建堆
        creatHeap(array);
        int end=array.length-1;
        //利用堆将数组进行排序。
        while(end>0){
            swap(array,0, end);
            shiftDown(array,0,end);
            end--;
        }


        return array;
    }

    public static void creatHeap(int[]array){
        int parent=((array.length-1)-1)/2;
        while(parent>=0){
            shiftDown(array,parent, array.length);
            parent--;
        }
    }

    /**
     * 从某一个节点向下调整
     * @param array
     * @param root 调整起始节点
     * @param len 调整结束判断条件(有效数组数据长度)
     */
   public static void shiftDown(int[] array,int root,int len){
        int parent=root;
        int child=parent*2+1;
       for (int i = child; i <len; ) {
            if(i+1<len&&array[i+1]>array[i]){
                i++;
            }
            if(array[i]>array[parent]){
                swap(array,parent,i);
                parent=i;
                i=parent*2+1;
            }else{
                break;
            }

       }
   }

    /**
     * 交换数组中两个下标元素值
     * @param array
     * @param i
     * @param j
     */
   public static void swap(int[]array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
   }
}